public class Test3 {
    //leetcode 96 不同的二叉搜索树
    public int numTrees(int n) {
        //同样动态规划只能解决组组合问题，要想解决这种排列问题，不是不可以用动态规划，因为动态规划可以将之前计算过的
        //结果记录下来，所以我们同样可以使用动态规划，那么如何抽象出来一个状态表示呢？
        //dp[i]表示有i个节点的时候有多少种二叉搜索树
        //当以n为根节点的时候，n节点的左子树的节点只能有n-1个，右子树只能有i-n个，所以以n为根节点的二叉搜索树
        //的种类有(n-1)*(i-n)种
        int[] dp = new int[n + 1];
        dp[0] = 1; //空子树也是二叉搜索树
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                dp[i] += dp[j-1] * dp[i-j];
            }
        }
        return dp[n];
    }
}
